////https://www.luogu.com.cn/problem/P4779 ������ȫͨ��
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int n, m, s;
int dis[100010], vis[100010];
//�����vis�����ʾĳ�������·�Ƿ��Ѿ�ȷ�����Ҹ��¹���Χ��һ��
//ʵ��������ɾ�����ߴ���
vector<pii> g[100010];
priority_queue<pii, vector<pii>, greater<pii> > q;

void dijk() {
    q.push(make_pair(0, s));
    dis[s] = 0;
    while (!q.empty()) {
        int now = q.top().second;
        q.pop();
        if (vis[now]) {
            continue;
        }
        vis[now] = 1;
        for (auto to : g[now]) {
            int v = to.second, w = to.first;
            if (dis[now] + w < dis[v]) {
                dis[v] = dis[now] + w;
                q.push({dis[v], v});
            }
        }
    }
    return;
}

int main() {
    scanf("%d%d%d", &n, &m, &s);
    int u, v, w;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({w, v});
    }
    memset(dis, 0x3f, sizeof(dis));
    dijk();
    for (int i = 1; i <= n; i++) {
        printf("%d%c", dis[i], (i == n) ? '\n' : ' ');  //δ��������ͨ���
    }
    return 0;
}
